snippet printb "Description" w
    void printBinary(int x) {
        string s;
        while (x) {
            if (x & 1) {
                s += '1';
            } else {
                s += '0';
            }
            x >>= 1;
        }
        reverse(s.begin(), s.end());
        cout << s << endl;
    }
endsnippet

snippet bipart_graph_match "二分图的最大匹配" w
// 二分图的最大匹配，时间复杂度O(n1 * 边数)
class bipart_graph_match {
public:
    vector<vector<int>>g;
    vector<int>vi, match;

    bipart_graph_match(int n): vi(n+1, 0), match(n+1){}

    bool find(int x) {
        for (auto j: g[x]) {
            if (vi[j] == 0) {
                vi[j] = 1;
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    int max_bipart_grath_match(vector<vector<int>>&g, int n1, int n2) {
        this->g = g;
        int ans = 0;
        for (int i = 1; i <= n1; i++){
            fill(vi.begin(), vi.end(), 0);
            if (find(i)) {
                ans++;
            }
        }
        return ans;
    }
};
endsnippet

snippet spfa "Description" w
// spfa求有负权的最短路，时间复杂度O(nm)
vector<int> spfa(vector<vector<pair<int, int>>>g, int be) {
    int len = g.size();
    vector<int>dis(len+1, INT_MAX);
    vector<int>vi(len+1, 0);
    queue<int>que;
    que.push(be);
    dis[be] = 0;
    vi[be] = 1;
    while (que.size()) {
        int f = que.front();
        que.pop();
        vi[f] = 0;
        for (auto i: g[f]) {
            int t = i.first, w = i.second;
            if (dis[f] + w < dis[t]) {
                dis[t] = dis[f] + w;
                if (vi[t] == 0) {
                    vi[t] = 1;
                    que.push(t);
                }
            }
        }
    }
    return dis;
}
endsnippet

snippet bellman_ford "有边数限制的最短路" w
struct node{
    int x, y, z;
};
// bellman_ford算法，求有边数限制的最短路问题，可以有负边和负权回路
// 输入：segs是边，be是起点，k是边树限制，range是点的范围
// 输出：有边数限制的最短路数组
vector<int> bellman(vector<node>&segs, int be, int k, int range) {
    vector<int>dis(range, INT_MAX);
    int len = segs.size();
    dis[1] = 0;
    for (int i = 0; i < k; i++){
        vector<int>bak(dis);
        for (int j = 0; j < len; j++){
            auto obj = segs[j];
            if (bak[obj.x] != INT_MAX) {
                dis[obj.y] = min(dis[obj.y], bak[obj.x] + obj.z);
            }
        }
    }
    return dis;
}
endsnippet

snippet qmi "快速幂" w
ll qmi(ll a, ll b, ll p) {
    using ll = long long;
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ret % p;
}
endsnippet

snippet max_rise_sequence "最大上升子序列" w
// 求最大上升子序列
// q数组下标代表对应长度的解空间，数值表示解空间中最小的末值
// 贪心的思想，使末值尽量小，时间复杂度为O(n * logn)
// 另外此题亦可用树状数组(或线段树)维护区间最大值，使用暴力dp求解，时间复杂度为(n * logn * logn)
int max_rise_sequence(vector<int>nums) {
    int len = nums.size();
    vector<int>q(len + 10);
    int cnt = 0;
    q[0] = INT_MIN;
    for (int i = 0; i < len; i++){
        int t = nums[i];
        int l = 0, r = cnt;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (q[mid] < t) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        q[l] = t;
        cnt = max(l, cnt);
    }
    return cnt;
}
endsnippet

snippet string_mod_cnt "最小编辑距离" w
int string_mod_cnt(string a, string b) {
    int len1 = a.size(), len2 = b.size();
    int f[len1+1][len2+1];
    a = ' ' + a, b = ' ' + b;
    memset(f, 0, sizeof f);
    for (int i = 0; i <= len1; i++){
        f[i][0] = i;
    }
    for (int i = 0; i <= len2; i++){
        f[0][i] = i;
    }

    for (int i = 1; i <= len1; i++){
        for (int j = 1; j <= len2; j++){
            f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
            if (a[i] == b[j]) {
                f[i][j] = min(f[i][j], f[i-1][j-1]);
            } else {
                f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
            }
        }
    }

    return f[len1][len2];
}
endsnippet

snippet imi "Description" w
INT_MIN
endsnippet

snippet ima "Description" w
INT_MAX
endsnippet

snippet  "Description" w
snippet max_same_sequence "最长公共子序列" w
int sequence(string a, string b) {
    int len1 = a.size(), len2 = b.size();
    int f[len1+1][len2+1];
    memset(f, 0, sizeof f);
    for (int i = 1; i <= len1; i++){
        for (int j = 1; j <= len2; j++){
            if (a[i-1] == b[j-1]) {
                f[i][j] = f[i-1][j-1] + 1;
            } else {
                f[i][j] = max(f[i-1][j], f[i][j-1]);
            }
        }
    }
    return f[len1][len2];
}
endsnippet

snippet vi "Description" w
using vi = vector<int>;
using vii = vector<vi>;
endsnippet

snippet bit_obj "树状数组维护区间最值" w
// 树状数组维护区间最值。支持操作：
// 1、单点修改 2. 区间查询。
// 复杂度均为O(logn * logn)，数据规模1e5内可用
// 注意下标从1开始
class bit {
public:
    vector<int>tree, nums; // 树状数组，原数组
    int n;

    bit(int x) : tree(x+1), nums(x+1), n(x) {}

    int lowbit(int x) {
        return x & -x;
    }

    int cmp(int a, int b) { // 目标条件，这里是最大值
        return max(a, b);
    }

    int query(int a, int b) { // 查询[a, b]之间的目标值
        int ret = nums[b];
        while (b >= a) {
            ret = cmp(ret, nums[b]);
            b--;
            for (; b - lowbit(b) >= a; b -= lowbit(b)){
                ret = cmp(ret, tree[b]);
            }
        }
        return ret;
    }

    void update(int idx, int v) { // 将下标为idx的数更新为v
        nums[idx] = v;
        tree[idx] = v;
        while (idx <= n) {
            int lx = lowbit(idx);
            for (int i = 1; i < lx; i <<= 1){
                tree[idx] = cmp(tree[idx], tree[idx- i]);
            }
            idx += lx;
        }
    }
};
endsnippet

snippet cl "Description" w
class $1 {
public:
	>++>
};
endsnippet

snippet exgcd "扩展欧几里得" w
// 扩展欧几里得，求最大公约数的同时
// 返回的x为逆元
>>>>>>> 38839cf6e07c0367f03bbc660d0bd97e93c0232f
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    } else {
        ll ret = exgcd(b, a % b, y, x);
        y -= a/b * x;
        return ret;
    }
}
endsnippet

snippet si "Description" w
size()
endsnippet

snippet lee "Description" b
class Solution{
public:
	$1
};
endsnippet

snippet en "Description" w
end()
endsnippet

snippet be "Description" w
begin()
endsnippet

snippet al "NormalAlgorithmProblem" b
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <limits.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;
void Init();
void Redirect();
using ll = long long;
using pii = pair<int, int>;

$1

void Init(){
	>++>
}

signed main(){
	// auto start_clock = clock();
	// ios::sync_with_stdio(false);
	Init();
	// auto end_clock = clock();
	// cout << "runtime: " << (double)(end_clock - start_clock)/CLOCKS_PER_SEC*1000 << "ms" << endl;
	return 0;
}

void Redirect(){
	freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
}
endsnippet

snippet so "Description" w
sort($1);
endsnippet

snippet f "MyFor" w
for ($1; >++>; >++>){
	>++>
}
endsnippet

snippet s "MyScanf" w
scanf("${1}", &>++>);
endsnippet

snippet p "MyPintf" w
printf("${1}">++>);
endsnippet

snippet lmax "Description" b
LLONG_MAX
endsnippet

snippet sol "Description" b
solve();
endsnippet

snippet mod "Description" b
const int MOD = 998244353;
endsnippet

snippet str "MyStruct" b
struct ${1}{
	>++>
}>++>;
endsnippet

snippet ope "stuctOperator" b
bool operator${1}(const >++> x) const{
	>++>
}
endsnippet

snippet tag "Description" b
printf("zzx\n");
endsnippet

snippet def "Description" b
#define ${1:} >++>
endsnippet

snippet inc "include" b
#include ${1:}
endsnippet

snippet mypow "Description" b
int mypow(int a, int b){
	if(b <= 2) return (a * a)%MOD;
	int ret1, ret2 = a, cnt1 = log(b)/log(2);
	int cnt2 = b - pow(2, cnt1);
	for(int i = 0; i < cnt1; ++i) ret2 = (ret2 * ret2)%MOD;
	return (jjpow(a, cnt2) * ret2)%MOD;
}
endsnippet

snippet myc "Description" b
int jjC(ll a, ll b){
	int ret = 1, tmp = 1;
	for(int i = a; i > a - b; --i) ret = (ret * i)%MOD;
	for(int i = 2; i <= b; ++i) tmp = (tmp * i)%MOD;
	return ret/tmp;
}
endsnippet

# A valid snippet should starts with:
#
#		snippet trigger_word [ "description" [ options ] ]
#
# and end with:
#
#		endsnippet
#
# Snippet options:
#
#		b - Beginning of line.
#		i - In-word expansion.
#		w - Word boundary.
#		r - Regular expression
#		e - Custom context snippet
#		A - Snippet will be triggered automatically, when condition matches.
#
# Basic example:
#
#		snippet emitter "emitter properties" b
#		private readonly ${1} = new Emitter<$2>()
#		public readonly ${1/^_(.*)/$1/}: Event<$2> = this.$1.event
#		endsnippet
#
# Online reference: https://github.com/SirVer/ultisnips/blob/master/doc/UltiSnips.txt
